package com.example.leetdemo.process;

import java.util.*;
import java.util.stream.Collectors;

public class Solution1847 {


    public int[] closestRoom(int[][] rooms, int[][] queries) {
        int[] resultArr = new int[queries.length];

        return resultArr;
    }

    /**
     * 这个超时了
     * @param rooms
     * @param queries
     * @return
     */
    public int[] closestRoom_plan1(int[][] rooms, int[][] queries) {
        int[] resultArr = new int[queries.length];
        List<int[]> list = new ArrayList<>();

        for (int i = 0; i < rooms.length; i++) {
            list.add(rooms[i]);
        }
        for (int i = 0; i < queries.length; i++) {
            int finalI = i;
            List<int[]> temp = list.stream().filter(a -> a[1] >= queries[finalI][1]).collect(Collectors.toList());
            if (temp.size() == 0) {
                resultArr[i] = -1;
            } else {
                temp.sort(Comparator.comparingInt(o -> o[0]));
                resultArr[i] = findNearestIndex(temp, queries[i][0]);
            }
        }
        return resultArr;
    }

    public int findNearestIndex(List<int[]> list, int k) {
        int left = 0, right = list.size() - 1;
        int nearestIndex = -1;
        int minDiff = Integer.MAX_VALUE;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            int diff = Math.abs(list.get(mid)[0] - k);
            if (diff < minDiff || (diff == minDiff && mid < nearestIndex)) {
                minDiff = diff;
                nearestIndex = mid;
            }
            if (list.get(mid)[0] < k) {
                left = mid + 1;
            } else if (list.get(mid)[0] > k) {
                right = right - 1;
            } else {
                return list.get(mid)[0];
            }
        }
        return nearestIndex == -1 ? list.get(list.size() - 1)[0] : list.get(nearestIndex)[0];
    }

    public static void main(String[] args) {
        int[][] rooms = new int[][] {
                {2,2},
                {1,2},
                {3,2}
        };
        int[][] queries = new int[][] {
                {3,1},{3,3}, {5,2}
        };
        Solution1847 solution1847 = new Solution1847();
        solution1847.closestRoom_plan1(rooms, queries);
    }

}
